`
https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
`

/**
 * @param {string} s
 * @return {number}
 */
var minInsertions = function (s) {
  const n = s.length

  // dp[i][j] 表示 s[i...j] 成为回文串的最少操作次数
  const dp = new Array(n).fill().map(() => new Array(n).fill(0))

  // 反着遍历保证正确的状态转移
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i + 1; j < n; j++) {
      if (s[i] === s[j]) {
        // 不需要插入任何字符
        dp[i][j] = dp[i + 1][j - 1]
      } else {
        // 把 s[i+1..j] 和 s[i..j-1] 变成回文串，选插入次数较少的
        // 然后还要再插入一个 s[i] 或 s[j]，使 s[i..j] 配成回文串
        dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1
      }
    }
  }

  // 整个 s 的最少插入次数
  return dp[0][n - 1]
};